package com.waiting.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/2/28
 **/
public class FourSum18 {
    public static void main(String[] args) {
        int[] nums = {0, 0, 0, 0};
        fourSum(nums, 0);
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new LinkedList<>();
        if (nums == null || nums.length < 4) {
            return result;
        }

        Arrays.sort(nums);
        for (int i = 0; i <= nums.length - 4; i++) {
            while (i >= 1 && nums[i] == nums[i - 1] && i <= nums.length - 4) {
                i++;
            }
            for (int j = i + 1; j <= nums.length - 3; j++) {
                while (j > i + 1 && nums[j] == nums[j - 1] && j <= nums.length - 3) {
                    j++;
                }
                int tmp = target - nums[i] - nums[j];
                int l = j + 1, h = nums.length - 1;
                int sum = nums[l] + nums[h];
                while (l < h) {
                    if (sum == tmp) {
                        List<Integer> oneResult = new LinkedList<>();
                        oneResult.add(nums[i]);
                        oneResult.add(nums[j]);
                        oneResult.add(nums[l]);
                        oneResult.add(nums[h]);
                        result.add(oneResult);
                        //
                        int ltmp = nums[l];
                        l++;
                        while (l < h && nums[l] == ltmp) {
                            l++;
                        }
                        ltmp = nums[h];
                        h--;
                        while (l < h && nums[h] == ltmp) {
                            h--;
                        }
                    }
                    sum = nums[l] + nums[h];
                    while (sum < tmp && l < h) {
                        l++;
                        sum = nums[l] + nums[h];
                    }
                    while (sum > tmp && l < h) {
                        h--;
                        sum = nums[l] + nums[h];
                    }
                }
            }
        }
        return result;
    }
}
